home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 422_02 / misc / prime1.c < prev    next >
C/C++ Source or Header  |  1994-03-20  |  920b  |  37 lines
  1. /*
  2.  * Much faster program for finding prime numbers. Each number is tested
  3.  * against previous primes, and the search is terminated when the
  4.  * square of the previous prime exceeds the number being tested.
  5.  *
  6.  * Note: 1 and 2 are neither tested nor displayed by this program.
  7.  *
  8.  * Compile command: cc prime1 -fop
  9.  */
  10. #include <stdio.h>
  11.  
  12. #define    MAXPRIME    1000        /* Search up to here */
  13.  
  14. unsigned primes[MAXPRIME/2], squares[MAXPRIME/2], count = 0;
  15.  
  16. /*
  17.  * Main (and only) function
  18.  */
  19. main()
  20. {
  21.     unsigned num, test;
  22.     char flag;
  23.  
  24.     for(num=3; num < MAXPRIME; num += 2) {    /* Test range */
  25.         flag = 1;
  26.         for(test = 0; test < count; ++test) {
  27.             if(squares[test] > num)            /* Out of range */
  28.                 break;
  29.             if(!(num % primes[test])) {        /* No remainder - Not prime */
  30.                 flag = 0;
  31.                 break; } }
  32.         if(flag) {
  33.             printf("%d\n", num);
  34.             primes[count] = num;
  35.             squares[count++] = num*num; } }
  36. }
  37.